#include <stdio.h>
#include <math.h>
#include <stdlib.h>

//https://leetcode.cn/problems/merge-two-sorted-lists/submissions/

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *cur1 = list1;
    struct ListNode *cur2 = list2;
    struct ListNode *preHead = malloc(sizeof(struct ListNode));    // 创建哨兵位
    struct ListNode *prev = preHead;
    preHead->next = NULL;
    while (cur1 && cur2) {
        if (cur1->val < cur2->val) {
            prev->next = cur1;
            cur1 = cur1->next;
        } else {
            prev->next = cur2;
            cur2 = cur2->next;
        }
        prev = prev->next;
    }
    prev->next = ((cur1 == NULL) ? cur2 : cur1);        // 至少有一个链表不为空，直接接到后面
    return preHead->next;
}

int main() {

    return 0;
}